By yusijia

Updated:

Contents
  • 回溯法解决
  • 题目去网上找吧，这个题太经典了
  • 参考：《算法竞赛入门经典》 作者：刘汝佳
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <cstdio>

int tot = 0, row, line[10], n;			//line[row]表示第row行，第line[row]列

void Search(int row);

int main()
{
    freopen("output.txt", "w", stdout);
    int a[11];
    while(scanf("%d", &n) != EOF && n){
        Search(0);
    }
    return 0;
}

void Search(int row)				//递归搜索可行解
{
    int i, j;
    if(row == n)                        	//当row=n时，说明每一行的皇后都不冲突，即为可行解
    {
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(j == line[i]){
                    printf("1 ");
                    continue;
                }
                printf("0 ");
            }
            printf("\n");
        }
        printf("\n\n");
    }
    else{
        for(i = 0; i < n; i++){
            bool istrue = true;
            line[row] = i;              	//尝试把第row行的皇后放在i列上
            for(j = 0; j < row; j++){  	 	//检验是否与前面已放好的皇后冲突
                if(line[row] == line[j] || line[row] - row == line[j] - j
                   || line[row] + row == line[j] + j){
                    istrue = false;		//line[row] - row == line[j] - j检查左上方,line[row] + row == line[j] + j检查右上方
                    break;			//列 - 行				   //列 + 行
                }
            }
            if(istrue)
                Search(row + 1);
        }
    }
}
Contents